import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2022-09-18
 * Time: 13:38
 */
public class Oj {
    /**
     * 直接使用异或
     * @param nums
     * @return
     */
    public int singleNumber1(int[] nums) {
        int tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            tmp = tmp^nums[i];
        }
        return tmp;

    }

    /**
     *使用map
     * @param nums
     * @return
     */
    public static int singleNumber2(int[] nums) {//使用map
        Map<Integer,Integer> map = new HashMap<>();
        //1.第一遍循环,将nums里的值全部放入map里
        for (int i = 0; i < nums.length; i++) {
            //如果map里不存在nums[i]
           if(!map.containsKey(nums[i])){
               map.put(nums[i],1);
           }else{//如果nums[i]已经存在
               int value = map.get(nums[i]);
               map.put(nums[i],value+1);
           }
        }
        //2.在map里寻找只出现一次的数字
       Set<Map.Entry<Integer,Integer>> entrySet =map.entrySet();
        for (Map.Entry<Integer,Integer> entry:entrySet){
            if (entry.getValue() == 1 ){
                int ret = entry.getKey();
                return ret;
            }
        }
      return -211111111;
    }

    /**
     * 使用set set里存放的是不重复的元素,在每次setadd之前,
     * 先判断一下set里面是否已经存在该元素,如果存在set里就删除,这样最后set里就只剩下只出现一次的元素了
     * @param args
     */
    public int singleNumber(int[] nums) {
     Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            //如果集合里有nums[i],就将原先集合里存在的nums[i]删除
            if(set.contains(nums[i])){
                set.remove(nums[i]);
                //如果集合里不存在nums[i],add
            }else {
                set.add(nums[i]);
            }
        }
//        Iterator<Integer> it= set.iterator();
//        while (it.hasNext()){
//
//        }
        //由于set里面没有提供可以获取key的方法,因此只能通过for循环在遍历一遍原先的数组来确定集合里的元素值
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                return nums[i];
            }
        }
        return -21111111;
    }


    class Node { int val;Node next;Node random;

        public Node(int val) {this.val = val;this.next = null;this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        //第一遍循环将全部的节点都拷贝一遍,并且通过map存储了每个节点开始对应的next和random
        while(cur != null){
            //产生新节点
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        //第二遍循环遍历,将拷贝的节点按照最开始的next和random连接起来
        cur = head;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
         }
        //返回头结点的value
        return map.get(head);
    }

    /**
     * 宝石和石头 利用set
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        //将jewels里的字符放入到set里
        char[] js = jewels.toCharArray();
        for (int i = 0; i < js.length; i++) {
            set.add(js[i]);
        }
        //计数器
        int count = 0;
        char[] ss = stones.toCharArray();
        for (int i = 0; i < ss.length; i++) {
            if (set.contains(ss[i])){
                count++;
            }
        }
        return count;
    }


    /**
     * 怀键盘
     */
    static void fun(String str1,String str2){
        //将实际输入的值全部输入到set2里
        Set<Character> set2 = new HashSet();
        for(char ch:str2.toUpperCase().toCharArray()){
            set2.add(ch);
        }
        Set<Character> set = new HashSet();
        for(char ch:str1.toUpperCase().toCharArray()){
            if(!set2.contains(ch) && !set.contains(ch)){
                System.out.print(ch);
                set.add(ch);
            }
        }
    }
//    public static void main(String[] args){
//        Set<Character> set = new HashSet();
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextLine()){
//            String s1 = sc.nextLine();//期望输入的
//            String s2 = sc.nextLine();//实际输入的
//            fun(s1,s2);
//        }
//    }

    /**
     *
     * @param words
     * @param k
     * @return
     */
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        //将words里的单词放入map里
        for(String s:words){
            if(!map.containsKey(s)){
                map.put(s,1);
            }else {
                int value = map.get(s);
                map.put(s,value+1);
            }
        }
        List<String> list = new ArrayList<>();
        //top_k 使用堆
        //建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minQ= new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //如果两个entry的value相同则,按题目要求得先poll字符序来比较,所以得先poll大字符
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }

                return o1.getValue().compareTo(o2.getValue()) ;//小根堆
            }
        });//默认小根堆 排序 必须传比较器
       Set<Map.Entry<String,Integer>> entrySet =  map.entrySet();
       for (Map.Entry<String,Integer> entry:entrySet){
           //堆里的元素个数如果小于k,先存k元素
           if (minQ.size()<k){
               minQ.add(entry);
           }else{//调整小根堆,这里是根据每个字符的value来调整
               if(entry.getValue().compareTo(minQ.peek().getValue())>0){
                   minQ.poll();
                   minQ.add(entry);
               }else{
                   // 1. < 这种情况不用调整堆    2.==,按照字典序来调整堆
                   if(entry.getValue().compareTo(minQ.peek().getValue()) == 0){
                       if(entry.getKey().compareTo(minQ.peek().getKey()) < 0){
                           minQ.poll();
                           minQ.add(entry);
                       }
                   }
               }
           }
       }
        for (int i = 0; i < k; i++) {
            list.add(minQ.poll().getKey());//按照小根堆 从小到大的顺序存list里
        }
        //输出的要求是按照从高到低 逆序
        Collections.reverse(list);
        return list;

}

    public static void main(String[] args) {
        //String[] s = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        String[] s = {"i", "love", "leetcode", "i", "love", "coding"};
        System.out.println(topKFrequent(s, 3));

    }

    public int firstUniqChar(String s) {
        int[] arr = new int[26];
        //第一遍 遍历 将s里的字符出现的次数统计起来
        for(char ch:s.toCharArray()){
            arr[ch - 97]++;
        }
        //第二遍 遍历 找出第一个唯一字符
        for (int i = 0; i <s.length(); i++) {
            char ch = s.charAt(i);
           if (arr[ch-97] ==1 ){
               return i;
           }
        }
        //代码走到这里,没有找到
        return -1;

    }
}
